package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150">验证回文串(Valid Palindrome)</a>
 * <p>
 * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
 * <p>
 * 字母和数字都属于字母数字字符。
 * </p>
 * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入: s = "A man, a plan, a canal: Panama"
 *      输出：true
 *      解释："amanaplanacanalpanama" 是回文串。
 *
 * 示例 2：
 *      输入：s = "race a car"
 *      输出：false
 *      解释："raceacar" 不是回文串。
 *
 * 示例 3：
 *      输入：s = " "
 *      输出：true
 *      解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。  由于空字符串正着反着读都一样，所以是回文串。
 * </pre>
 * </p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 2 * 10^5</li>
 *     <li>s 仅由可打印的 ASCII 字符组成</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/10/10 16:47
 */
public class LC0125ValidPalindrome_S {

    static class Solution {
        public boolean isPalindrome(String s) {
            // 移除所有的非数字与非字母
            StringBuilder realStr = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char curChar = s.charAt(i);
                if ('A' <= curChar && curChar <= 'Z') {
                    realStr.append((char) (curChar + 32));
                } else if (('a' <= curChar && 'z' >= curChar) || ('0' <= curChar && '9' >= curChar)) {
                    realStr.append(curChar);
                }
            }
            // 双指针判断回文串
            int left = 0;
            int right = realStr.length() - 1;
            while (left < right) {
                if (realStr.charAt(left) != realStr.charAt(right)) {
                    return false;
                }
                ++left;
                --right;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPalindrome("A man, a plan, a canal: Panama"));
        System.out.println(solution.isPalindrome("race a car"));
        System.out.println(solution.isPalindrome(" "));
    }
}
